Mỗi nút của cây đỏ-đen có thuộc tính "màu" nhận một trong hai giá trị "đỏ" hoặc "đen". Ngoài ra:

1. Một nút hoặc là đỏ hoặc là đen.
2. Gốc là đen.
3. Tất cả các lá (NULL) là đen.
4. Cả hai con của mọi nút đỏ là đen. (và suy ra mọi nút đỏ có nút cha là đen)
5. Tất cả các đường đi từ một nút bất kỳ tới các lá có số nút đen bằng nhau.

Tính chất 5 còn được gọi là tính chất "cân bằng đen". Số các nút đen trên một đường đi từ gốc tới mỗi lá được gọi là độ dài đen của đường đi đó. Trong bài này chỉ xét các đường đi từ gốc tới các lá nên ta sẽ gọi tắt các đường đi như vậy là đường đi.Sức mạnh của cây đỏ đen nằm trong các tính chất trên. Từ các tính chất này suy ra trong các đường đi từ gốc tới các lá đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất. Do đó cây đỏ đen là gần cân bằng. Vì các thuật toán chèn, xóa, tìm kiếm trong trường hợp xấu nhất đều tỷ lệ với chiều cao của cây nên cây đỏ đen rất hiệu quả trong các trường hợp xấu nhất,không giống như cây tìm kiếm nhị phân thông thường.

Để thấy rõ sức mạnh này, ta chú ý rằng không có đường đi nào từ gôc tới một lá chứa hai nút đỏ liền nhau (theo tính chất 4). Do đó trên mỗi đường số nút đỏ không nhiều hơn số nút đen. Đường đi ngắn nhất là đường đi chỉ có nút đen, đường đi dài nhất có thể là đường đi xen kẽ giữa các nút đỏ và đen. Theo tính chất 5, số các nút đen trên hai đường đi đó bằng nhau, và do đó đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất.

Trong nhiều biểu diễn của dữ liệu cây, có thể có các nút chỉ có một con và có các lá có chứa dữ liệu. Tuy nhiên có thể biểu diễn cây đỏ đen ta có một chút thay đổi mà không làm thay đổi tính chất cơ bản của cây và độ phức tạp của các thuật toán. Với mục đích này, ta đưa thêm các lá null vào làm con phải hoặc con trái hoặc cả hai của những nút không có chúng, các lá này không chứa dữ liệu mà chỉ làm nhiệm vụ thông báo rằng tại đây cây đã kết thúc, như hình vẽ ở trên. Việc thêm các nút này làm cho tất cả các nút trong của cây đều chứa dữ liệu và có hai con, hay khác đi cây đỏ đen cùng với các lá null là cây nhị phân đầy dủ. Khi đó số các "lá null" nhiều hơn số các nút chứa dữ liệu của cây một lá.

Một số người định nghĩa cây đỏ đen bằng cách gán màu đỏ đen cho các cạnh chứ không phải các nút. Tuy nhiên điều đó không tạo nên sự khác biệt. Khi ấy màu của mỗi nút tương ứng với màu của cạnh nối nó với nút cha.